package com.lzy.algorithm;

import java.util.Arrays;

/**
 * Author: lzy
 * Date:   2020/06/20 16:02
 * Description:
 **/
public class 堆排序 {

    public static void genHeap(int[] nums, int parentIndex, int length) {

        int temp = nums[parentIndex];
        int childIndex = 2 * parentIndex + 1;

        while (childIndex < length) {

            // 选取子节点中大的那个
            if (childIndex + 1 < length && nums[childIndex + 1] > nums[childIndex]) {
                childIndex++;
            }
            // 父节点比子节点大，跳过
            if(temp >= nums[childIndex]){
                break;
            }

            nums[parentIndex] = nums[childIndex];
            parentIndex = childIndex;
            childIndex = childIndex * 2 + 1;
        }

        nums[parentIndex] = temp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 18, 45, 23, 9, 6, 11, 1};

        // 把无序数组创建成大顶堆
        for (int i = (nums.length - 2) / 2; i >= 0; i--) {
            genHeap(nums, i, nums.length);
        }
        System.out.println(Arrays.toString(nums));

        // 堆顶和最后一个元素依次替换，替换后重新建堆
        for (int i = nums.length - 1; i > 0; i--) {
            int temp = nums[i];
            nums[i] = nums[0];
            nums[0] = temp;

            genHeap(nums, 0, i);
        }
        System.out.println(Arrays.toString(nums));
    }

}
